package leetcode;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-12-13 13:47
 **/
public class LeetCode807 {

    public int maxIncreaseKeepingSkyline(int[][] grid) {
        int n = grid.length;
        //rowMax[i]: 行最大值
        int[] rowMax = new int[n];
        //colMax[i]: 列最大值
        int[] colMax = new int[n];
        //遍历二维数组,记录每行每列的最大值
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                rowMax[i] = Math.max(rowMax[i], grid[i][j]);
                colMax[j] = Math.max(colMax[j], grid[i][j]);
            }
        }
        int res = 0;
        //只要grid[i][j]不大于i行j列的最大值即可,将可添加的高度计入res中
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                res += Math.min(rowMax[i], colMax[j]) - grid[i][j];
            }
        }
        return res;
    }

}
